# 热题100 https://leetcode.cn/studyplan/top-100-liked/
# 4/100 双指针-移动零
# leetcode第283题: https://leetcode.cn/problems/move-zeroes/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/11/13

def moveZeroes(nums: list[int]) -> list[int]:
    """将0视为空位并用后面的元素依次填充"""
    i, j, n = 0, 0, len(nums)
    while i < n and j < n:
        if nums[i] == 0:
            for k in range(i, n - 1):
                nums[k] = nums[k + 1]
            nums[n - 1] = 0
        else:
            i += 1
        j += 1
    return nums


def moveZeroes_additional(nums: list[int]) -> list[int]:
    """使用一个额外的数组作为保存, 这个函数可以帮助更好的理解下面双指针的方法"""
    res, cnt = [], 0
    for i in range(len(nums)):
        if nums[i] != 0:
            res.append(nums[i])
        else:
            cnt += 1  # cnt用于记录0的数量
    for _ in range(cnt):
        res.append(0)
    return res


def moveZeroes_dbpnt(nums: list[int]) -> list[int]:
    """使用双指针的方法-快慢指针:
    1. 右指针不间断的由左向右移动, 左指针只在右指针不为0的时候移动
        1  2  0  0  3  4      1  2  0  0  3  4
        lr                       lr
    2. 如果前n项均为非0的数字, 则左右指针始终指向同一元素, 直到右指针找到第一个为0的数字
    3. 右指针找到第一个为0的数字后, 左指针指向这个0, 右指针继续移动直到一个非0的数字后, 交换两个数字的位置, 左指针继续向右
        1  2  0  0  3  4      1  2  0  0  3  4      1  2  3  0  0  4
              lr                    l     r                  l  r
    4. 由于右指针指向非0才交换, 而根据3.的条件, 左指针在交换之前必定停留在0元素位置, 那么交换过后则左指针必定指向非0, 右指针指向0.
       这样就可以保证在交换的时候, 左指针始终指向0元素, 而右指针则指向非0元素
        1  2  3  0  0  4      1  2  3  4  0  0
                 l     r                  l  r
    """
    n = len(nums)
    l = r = 0
    while r < n:
        if nums[r] != 0:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
        r += 1
    return nums


"""快慢指针
在什么情况下使用快慢指针?
当我们需要将一个数组的内容按照条件过滤成为一个子数组的时候, 且原数组的内容不再被需要的时候, 可以使用快慢指针来进行遍历
快慢指针有什么好处?
可以减少申请额外的空间.
到底什么是快慢指针?
在遍历一个数组的时候, 如果原始数组中的每一项一旦遍历过就不在被需要了, 那么这些被遍历过的数组就可以当做临时数组去使用.
所谓快慢指针就是我们需要两个指针, 快的指针指向当前正在遍历的元素位置, 慢的指针是当前临时数组中最后一个元素的位置, 
通过这种方式我们可以使用O(1)的空间复杂度的方式去完成对数组内容的过滤
快慢指针: 用于对数组的原地过滤
滑动窗口: 用来解决区间最值问题, 或求一个满足条件的子区间
双指针: 主要用来解决需要数组前后进行比较交换的问题
详细可以查看下面的视频
https://www.bilibili.com/video/BV1Z3pReYEkK/
"""

if __name__ == '__main__':
    print(moveZeroes_dbpnt([0, 1, 0, 3, 12]))  # [1, 3, 12, 0, 0]
    print(moveZeroes_dbpnt([0, 0, 1]))  # [1, 0, 0]
    print(moveZeroes_additional([0, 1, 0, 3, 12]))  # [1, 3, 12, 0, 0]
    print(moveZeroes_additional([0, 0, 1]))  # [1, 0, 0]
